#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL y,z,p;
map <LL,LL> tab;
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}
LL qpow(LL a,LL b,LL MOD)
{
    LL ans=1;
    for(;b;b>>=1,a=a*a%MOD)
        if(b&1)ans=ans*a%MOD;
    return ans;
}
void exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    LL t=x;
    x=y;
    y=t-a/b*y;
    return;
}
void BSGS(LL y,LL z,LL p)
{
    y%=p;z%=p;
    tab.clear();
    LL m=ceil(sqrt(p));
    if(!y)
    {
        if(!z)printf("1\n");
        else printf("Orz, I cannot find x!\n");
        return;
    }
    else
    {
        if(z==1)
        {
            printf("0\n");
            return;
        }
    }
    LL k=z%p,temp=qpow(y,m,p);
    tab[z]=m;
    for(LL j=1;j<m;++j)
    {
        k=k*y%p;
        if(!tab[k])tab[k]=j;
    }
    k=1;
    for(LL i=1;i<=m+1;++i)
    {
        k=k*temp%p;
        if(tab[k])
        {
            printf("%lld\n",i*m-(tab[k]%m));
            return;
        }
    }
    printf("Orz, I cannot find x!\n");
    return;
}
int main()
{
    LL T,k;
    scanf("%lld%lld",&T,&k);
    while(T--)
    {
        scanf("%lld%lld%lld",&y,&z,&p);
        if(k==1)printf("%lld\n",qpow(y,z,p));
        else if(k==3)BSGS(y,z,p);
        else
        {
            LL t=gcd(y,p);
            if(z%t)
            {
                printf("Orz, I cannot find x!\n");
                continue;
            }
            y/=t;z/=t;p/=t;
            LL a,b;
            exgcd(y,p,a,b);
            a=a*z%p;
            while(a<0)a+=p;
            printf("%lld\n",a);
        }
    }
    return 0;
}
